////////////////////////////////////////////////////////////////////////////
//
//  Crytek Engine Source File.
//  Copyright (C), Crytek Studios, 2007.
// -------------------------------------------------------------------------
//  File name:   AreaGrid.h
//  Version:     v1.00
//  Created:     08/03/2007 by Michael Smith.
//  Compilers:   Visual Studio.NET 2005
//  Description: 
// -------------------------------------------------------------------------
//  History:
//
////////////////////////////////////////////////////////////////////////////

#include "StdAfx.h"
#include "AreaGrid.h"
#include "Area.h"
#include <IRenderAuxGeom.h>

const uint32 CAreaGrid::GRID_CELL_SIZE = 4;
const float CAreaGrid::GRID_CELL_SIZE_R = 1.f / CAreaGrid::GRID_CELL_SIZE;

//
// Area Bit Field
//
// 1 bit per area, bit field size is determined by num areas;
uint32	CAreaBitField::s_bitFieldSizeU32=1;
uint32	CAreaBitField::s_maxNumAreas=1;
uint32* CAreaBitField::s_pBitArrayMem=NULL;
uint32* CAreaBitField::s_pBitArrayMemCurrent=NULL;
uint32	CAreaBitField::s_nGridCells=0;
uint32* CAreaBitField::s_pAreaList=NULL;
uint32*	CAreaBitField::s_pTempBitMem=NULL;

CAreaBitField::CAreaBitField()
{
	assert(s_pBitArrayMemCurrent);
	assert(s_pBitArrayMemCurrent<(s_pBitArrayMem+(s_bitFieldSizeU32*s_nGridCells*2)));

	//allocate bit array from global pool
	m_pbitField = s_pBitArrayMemCurrent;
	s_pBitArrayMemCurrent += s_bitFieldSizeU32;
	
	memset(m_pbitField, 0, s_bitFieldSizeU32*sizeof(uint32));
}

CAreaBitField::~CAreaBitField()
{
	//Does not own m_pbitField
}

void CAreaBitField::SetArea(uint32 areaIndex)
{
	//check we're in range
	assert(areaIndex<s_bitFieldSizeU32*32);

	//divide by 32 to get bucket
	uint32 bucketIndex = areaIndex >> 5; 

	//get the offset into the given bucket
	uint32 bucketBit = 1 << (areaIndex - (bucketIndex * 32));

	m_pbitField[bucketIndex] |= bucketBit;
}

void CAreaBitField::ClearArea(uint32 areaIndex)
{
	assert(areaIndex<s_bitFieldSizeU32*32);

	uint32 bucketIndex = areaIndex >> 5; 
	uint32 bucketBit = 1 << (areaIndex - (bucketIndex * 32));

	m_pbitField[bucketIndex] &= ~bucketBit;
}

bool CAreaBitField::CheckArea(uint32 areaIndex)
{
	assert(areaIndex<(s_bitFieldSizeU32*32));

	uint32 bucketIndex = areaIndex >> 5; 
	uint32 bucketBit = 1 << (areaIndex - (bucketIndex * 32));

	return (m_pbitField[bucketIndex] & bucketBit) ? true : false;
}

//static
uint32* CAreaBitField::GetAreas(CAreaBitField &lhs, CAreaBitField& rhs, uint32 &nAreasOut)
{
	//& bit fields 
	for(uint32 i=0; i<s_bitFieldSizeU32; i++)
	{
		s_pTempBitMem[i] = lhs.m_pbitField[i] & rhs.m_pbitField[i];
	}

	uint32 currentAreaIndex=0;
	uint32 numAreas=0;

	for(uint32 i=0; i<s_bitFieldSizeU32; i++)
	{
		uint32 currentBitField=s_pTempBitMem[i];

		if(currentBitField!=0)
		{
			uint32 checkBit = 1;

			for(uint32 j=0; j<32; j++)
			{
				if(currentBitField & checkBit)
				{
					s_pAreaList[numAreas++] = currentAreaIndex;
				}
				currentAreaIndex++;
				checkBit<<=1;
			}
		}
		else
		{
			currentAreaIndex+=32;
		}
	}

	nAreasOut = numAreas;

	return s_pAreaList;
}

//static 
void CAreaBitField::InitGrid(uint32 nAreas, uint32 nGridCells)
{
	//see how many u32's we need to store all areas
	s_bitFieldSizeU32 = ((nAreas+31)>>5);
	s_maxNumAreas = nAreas;
	s_nGridCells = nGridCells;

	AllocateMem();
}

//static
void CAreaBitField::AllocateMem()
{
	assert(s_pBitArrayMem==NULL&&s_pAreaList==NULL&&s_pTempBitMem==NULL);

	//allocate all mem for bit arrays (both x and y slice)
	int nU32s = s_bitFieldSizeU32 * s_nGridCells * 2;

	s_pBitArrayMem = new uint32[nU32s];
	s_pBitArrayMemCurrent = s_pBitArrayMem;

	s_pAreaList = new uint32[s_maxNumAreas];
	s_pTempBitMem = new uint32[s_bitFieldSizeU32];
}

//static
void CAreaBitField::FreeMem()
{
	SAFE_DELETE_ARRAY(s_pBitArrayMem)
	s_pBitArrayMemCurrent=NULL;

	SAFE_DELETE_ARRAY(s_pAreaList);
	SAFE_DELETE_ARRAY(s_pTempBitMem);
}

//
// Area Grid
//


CAreaGrid::CAreaGrid(): 
m_pAreas(0), 
m_pEntitySystem(0),
m_areaSliceX(NULL),
m_areaSliceY(NULL),
m_nCells(1000)
{
}

void CAreaGrid::Compile(CEntitySystem* pEntitySystem, std::vector<CArea*>& areas)
{
	FUNCTION_PROFILER( GetISystem(),PROFILE_ENTITY );

	Reset();

	//No point creating an area grid if there are no areas
	if(areas.size()==0)
	{
		return;
	}

	uint32 terrainSize = gEnv->p3DEngine->GetTerrainSize();

	m_nCells = terrainSize / GRID_CELL_SIZE;

	m_nCells = max(m_nCells, (uint32)512);

	CAreaBitField::InitGrid(areas.size(), m_nCells);

	m_areaSliceX = new CAreaBitField[m_nCells];
	m_areaSliceY = new CAreaBitField[m_nCells];

	m_pEntitySystem = pEntitySystem;

	// Loop through all the grid cells that might be covered.
	std::vector<int> areaIndexList; // Declare some vectors out here so we don't keep freeing the memory and reallocating.
	for (int areaToStepThroughIndex = 0, areaToStepThroughCount = areas.size(); areaToStepThroughIndex < areaToStepThroughCount; ++areaToStepThroughIndex)
	{
		CArea* const pAreaWhoseBoundingBoxToStepThrough = areas[areaToStepThroughIndex];

		// Calculate a loose bounding box (ie one that covers all the region we will have to check this
		// shape for, including fade area).
		Vec2 vBBCentre(0, 0);
		Vec2 vBBExtent(0, 0);
		switch (pAreaWhoseBoundingBoxToStepThrough ? pAreaWhoseBoundingBoxToStepThrough->GetAreaType() : EEntityAreaType(-1))
		{
		case ENTITY_AREA_TYPE_SPHERE:
			{
				Vec3 vSphereCentre(ZERO);
				float fSphereRadius(0.0f);
				if (pAreaWhoseBoundingBoxToStepThrough)
					pAreaWhoseBoundingBoxToStepThrough->GetSphere(vSphereCentre, fSphereRadius);
				vBBCentre = Vec2(vSphereCentre.x, vSphereCentre.y);
				float fMaxEffectiveRadius = GetMaximumEffectRadius(pAreaWhoseBoundingBoxToStepThrough);
				vBBExtent = Vec2(fSphereRadius + fMaxEffectiveRadius, fSphereRadius + fMaxEffectiveRadius);
			}
			break;

		case ENTITY_AREA_TYPE_SHAPE:
			{
				Vec2 vShapeMin, vShapeMax;
				pAreaWhoseBoundingBoxToStepThrough->GetBBox(vShapeMin, vShapeMax);
				vBBCentre = (vShapeMax + vShapeMin) * 0.5f;
				float fMaxEffectiveRadius = GetMaximumEffectRadius(pAreaWhoseBoundingBoxToStepThrough);
				vBBExtent = (vShapeMax - vShapeMin) * 0.5f + Vec2(fMaxEffectiveRadius, fMaxEffectiveRadius);
			}
			break;

		case ENTITY_AREA_TYPE_BOX:
			{
				Vec3 vBoxMin, vBoxMax;
				pAreaWhoseBoundingBoxToStepThrough->GetBox(vBoxMin, vBoxMax);
				Matrix34 tm;
				pAreaWhoseBoundingBoxToStepThrough->GetMatrix(tm);
				static const float sqrt2 = 1.42f;
				float fMaxEffectiveRadius = GetMaximumEffectRadius(pAreaWhoseBoundingBoxToStepThrough);
				const Vec3 vBoxMinWorld = tm.TransformPoint(vBoxMin);
				const Vec3 vBoxMaxWorld = tm.TransformPoint(vBoxMax);
				vBBExtent = Vec2(abs(vBoxMaxWorld.x - vBoxMinWorld.x), abs(vBoxMaxWorld.y - vBoxMinWorld.y)) * sqrt2 * 0.5f;
				vBBExtent += Vec2(fMaxEffectiveRadius, fMaxEffectiveRadius);
				vBBCentre = Vec2(vBoxMinWorld.x + vBoxMaxWorld.x, vBoxMinWorld.y + vBoxMaxWorld.y) * 0.5f;
			}
			break;
		}

		//Covert BB pos into grid coords
		int gridMinX = (int)(floor((vBBCentre.x - vBBExtent.x) * GRID_CELL_SIZE_R));
		int gridMaxX = (int)(floor((vBBCentre.x + vBBExtent.x) * GRID_CELL_SIZE_R));
		int gridMinY = (int)(floor((vBBCentre.y - vBBExtent.y) * GRID_CELL_SIZE_R));
		int gridMaxY = (int)(floor((vBBCentre.y + vBBExtent.y) * GRID_CELL_SIZE_R));

		bool bClamped = false;

		if(gridMinX < 0 || gridMinY < 0 || gridMaxX >= (int)m_nCells || gridMaxY >= (int)m_nCells)
		{
			//Can cause spam in some levels were many areas exceed area grid
			//CryWarning(VALIDATOR_MODULE_ENTITYSYSTEM, VALIDATOR_WARNING, "[Area Manager] Area BB exceeds grid area! - clamping\n");

			gridMinX = max(gridMinX, 0);
			gridMinY = max(gridMinY, 0);
			gridMaxX = min(gridMaxX, (int)m_nCells-1);
			gridMaxY = min(gridMaxY, (int)m_nCells-1);

			bClamped = true;
		}

		for(int i=gridMinX; i<=gridMaxX; i++)
		{
			m_areaSliceX[i].SetArea(areaToStepThroughIndex);
		}
		
		for(int i=gridMinY; i<=gridMaxY; i++)
		{
			m_areaSliceY[i].SetArea(areaToStepThroughIndex);
		}

#ifndef _RELEASE
		//query bb extents to see if they are correctly added to the grid
		//Debug_CheckBB(vBBCentre, vBBExtent, areaToStepThroughIndex);
#endif
	}

	m_pAreas = &areas;
}

void CAreaGrid::Reset()
{
	CAreaBitField::FreeMem();

	SAFE_DELETE_ARRAY(m_areaSliceX);
	SAFE_DELETE_ARRAY(m_areaSliceY);
	
	m_pAreas = NULL;
}

uint32* CAreaGrid::GetAreas(const Vec3& position, uint32& nAreas)
{
	if (m_areaSliceX == NULL || m_areaSliceY == NULL)
	{
		nAreas = 0;
		return NULL;
	}

	int gridX = (int)(position.x * GRID_CELL_SIZE_R);
	int gridY = (int)(position.y * GRID_CELL_SIZE_R); 

	if(gridX<0 || gridX>=(int)m_nCells || gridY<0 || gridY>=(int)m_nCells)
	{
		//printf("Trying to index outside of grid\n");
		nAreas = 0;
		return NULL;
	}

	return CAreaBitField::GetAreas(m_areaSliceX[gridX], m_areaSliceY[gridY], nAreas);
}

void CAreaGrid::Draw()
{
	if (!m_pAreas)
		return;

//Crashes in aux geom renderer - mem alloc, probably trying to draw too many tri's
























































	
	float yPos=300.f;
	float fColor[4]={1.0f, 1.0f, 1.0f, 1.f};

	gEnv->pRenderer->Draw2dLabel(30, yPos, 1.35f, fColor, false, "Area Grid Mem Use: num cells: %d, memAlloced: %.2fk", 
																m_nCells, (4*CAreaBitField::GetBitFieldSizeU32()*m_nCells*2)/1024.f);

}

float CAreaGrid::GetMaximumEffectRadius(CArea *pArea)
{
	float fMaxRadius = 0.0f;

	const std::vector<EntityId>& entIDs=*pArea->GetEntities();

	// Check all Entities.
	for (uint32 i = 0; i < entIDs.size(); i++)
	{
		int entityId = entIDs[i];
		IEntity* pEntity = (m_pEntitySystem ? m_pEntitySystem->GetEntity(entityId) : 0);
		if (pEntity)
		{
			IEntitySoundProxy* pSoundProxy = (IEntitySoundProxy*)pEntity->GetProxy(ENTITY_PROXY_SOUND);
			if (pSoundProxy)
			{
				fMaxRadius = max(fMaxRadius, pSoundProxy->GetEffectRadius());
			}
		}
	}

	return fMaxRadius;
}

#ifndef _RELEASE
void CAreaGrid::Debug_CheckBB(Vec2 &vBBCentre, Vec2 &vBBExtent, uint32 areaIndex)
{
	uint32 nAreas=0;

	Vec2 minPos(vBBCentre.x - vBBExtent.x, vBBCentre.y - vBBExtent.y);
	uint32 *pAreaList = GetAreas(minPos, nAreas);
	bool bFoundMin = false;

	for(uint32 i=0; i<nAreas; i++)
	{
		if(pAreaList[i] == areaIndex)
		{
			bFoundMin = true;
			break;
		}
	}

	Vec2 maxPos(vBBCentre.x + vBBExtent.x, vBBCentre.y + vBBExtent.y);
	pAreaList = GetAreas(maxPos, nAreas);
	bool bFoundMax = false;

	for(uint32 i=0; i<nAreas; i++)
	{
		if(pAreaList[i] == areaIndex)
		{
			bFoundMax = true;
			break;
		}
	}

	//caveat: this may fire if the area was clamped
	if((!bFoundMin || !bFoundMax) /*&& !bClamped*/)
	{
		CryLogAlways("Error: AABB extent was not found in grid\n");
	}
}
#endif